package leetcode.editor.cn;
import java.util.*;
//给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的
//句子。 
//
// 说明： 
//
// 
// 分隔时可以重复使用字典中的单词。 
// 你可以假设字典中没有重复的单词。 
// 
//
// 示例 1： 
//
// 输入:
//s = "catsanddog"
//wordDict = ["cat", "cats", "and", "sand", "dog"]
//输出:
//[
//  "cats and dog",
//  "cat sand dog"
//]
// 
//
// 示例 2： 
//
// 输入:
//s = "pineapplepenapple"
//wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
//输出:
//[
//  "pine apple pen apple",
//  "pineapple pen apple",
//  "pine applepen apple"
//]
//解释: 注意你可以重复使用字典中的单词。
// 
//
// 示例 3： 
//
// 输入:
//s = "catsandog"
//wordDict = ["cats", "dog", "sand", "and", "cat"]
//输出:
//[]
// 
// Related Topics 字典树 记忆化搜索 哈希表 字符串 动态规划 回溯 👍 506 👎 0

public class 单词拆分II{
	public static void main(String[] args) {
		Solution solution = new 单词拆分II().new Solution();
		ArrayList<String> wordDict = new ArrayList<>();
		wordDict.add("apple");
		wordDict.add("pen");
		wordDict.add("applepen");
		wordDict.add("pine");
		wordDict.add("pineapple");
		solution.wordBreak("pineapplepenapple",wordDict);
	}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
		this.wordDict = wordDict;
		this.results = new ArrayList<>();
		this.trie = new Trie();
		trie.insert(s);
		backTrack(new ArrayList<>(), trie);
		return results;

	}
	public Trie trie;
    public List<String> wordDict;
    public List<String> results;

    public void backTrack(List<String> path, Trie status){
		System.out.println(path.size());
    	if(status.isEnd){
			StringBuilder result = new StringBuilder(path.get(0));
			for (int i = 1; i < path.size(); i++) {
				result.append(" ").append(path.get(i));
			}
    		results.add(new String(result));
    		return;
		}
    	for (String s : wordDict) {
			Trie node = status.searchPrefix(s);
			if(node!=null){
				path.add(s);
				backTrack(path, node);
				path.remove(path.size()-1);
			}
		}
	}

	class Trie {
		private Trie[] children;
		private boolean isEnd;
		/** Initialize your data structure here. */
		public Trie() {
			children = new Trie[26];
			isEnd = false;
		}

		/** Inserts a word into the trie. */
		public void insert(String word) {
			Trie node = this;
			for (int i = 0; i < word.length(); i++) {
				char c = word.charAt(i);
				int index = (int) (c - 'a');
				if(node.children[index] == null){
					node.children[index] = new Trie();
				}
				node = node.children[index];
			}
			node.isEnd = true;
		}

		/** Returns if the word is in the trie. */
		public boolean search(String word) {
			Trie node = searchPrefix(word);
			return node!=null && node.isEnd;
		}

		/** Returns if there is any word in the trie that starts with the given prefix. */
		public boolean startsWith(String prefix) {
			Trie node = searchPrefix(prefix);
			return node!=null;
		}

		public Trie searchPrefix(String prefix) {
			Trie node = this;
			for (int i = 0; i < prefix.length(); i++) {
				char ch = prefix.charAt(i);
				int index = ch - 'a';
				if (node.children[index] == null) {
					return null;
				}
				node = node.children[index];
			}
			return node;
		}

	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
